# 给定一个整型数组和一个数字 s，找到数组中最短的一个连续子数组，使得连续子数组的数字和 sum >= s，返回这个最短的连续子数组的长度值
# - 如，给定数组[2,3,1.2.4.3]，s=7
# - 答案为 [4,3]，返回 2
# 如果没有解怎样？保证有解
# 如果有多个解怎样？返回任意解


def minSubArrayLen(nums, s):
    # 双指针
    # j 和 i 从 0 开始跑，j 先跑，找到大于s的数则 i + 1，小于 s 则 j + 1
    i, j, r = 0, 0, len(nums) + 1  # i: i 指针，j 指针，r 记录最短长度
    sums = []  # 通过创建一个和数组来将求和的复外度从O(N)减到O(1)
    for num in nums:
        if not sums:
            sums.append(num)
        else:
            sums.append(sums[-1] + num)
    while i < len(nums) and j < len(nums):
        if sums[j] - sums[i] + nums[i] < s:
            j += 1
        else:
            if j + 1 - i < r:
                r = j + 1 - i
            i += 1
    if r != len(nums) + 1:
        return r
    else:
        return 0


if __name__ == '__main__':
    print(minSubArrayLen([2, 3, 1, 2, 4, 3], 7))
